package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-10
 * Time:14:53
 */

/**
 * 力扣面试经典150:76. 最小覆盖子串
 * 困难
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 注意：
 *     对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 *     如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * 示例 1：
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 */
public class minWindow {
    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }
    public static String minWindow(String s, String t) {
//        if (s.length() < t.length()) {
//            return "";
//        }
//        int[] arr = new int['z' - 'A' + 1];
//        for (char c : t.toCharArray()) {
//            arr[c - 'A']++;
//        }
//        int cnt = t.length();
//        int begin = -1;
//        int count = s.length() + 1;
//        char[] chars = s.toCharArray();
//        int l = 0;
//        int r = 0;
//        while (r < s.length()) {
//            if (arr[chars[r++] - 'A']-- > 0) {
//                cnt--;
//            }
//            if (cnt == 0) {
//                while (arr[chars[l] - 'A']++ < 0) {
//                    l++;
//                }
//                if (count > r - l) {
//                    begin = l;
//                    count = r - l;
//                }
//                l++;
//                cnt++;
//            }
//        }
//        return begin == -1 ? "" : new String(chars, begin, count);
        int lent = t.length();
        int lens = s.length();
        int count = lens + 1;
        int[] chars = new int['z' - 'A' + 1];
        //对应 t 中的字母的位置和个数
        for(char c:t.toCharArray()){chars[c - 'A']++;}
        int left = 0;int right = 0;int start = -1;
        while(right < lens){
            //滑动窗口，当窗口在 s 中滑动的时候遇到 t 中的字符就在 chars 对应位置--
            if(chars[s.charAt(right++) - 'A']-- > 0) lent--;
            //此时已经在 s 中找到所有的 t 中的字符了
            if(lent == 0){
                //因为要滑动，所以在向右滑动时 left 位置如果是 t 中字符需要在数组对应位置++或已经确定不是 t 中字符就 left++
                while (chars[s.charAt(left) - 'A']++ < 0) {
                    left++;
                }
                //count 就是记录此时符合条件的长度，当长度大于此时得到的长度就赋值
                if (count > right - left) {
                    start = left;
                    count = right - left;
                }
                left++;
                lent++;
            }
        }
        return start == -1 ? "" : s.substring(start,count + start);
    }
}
